package 二叉树相关问题.BST;

import java.util.ArrayList;
import java.util.List;

public class 两数之和4 {
    List<Integer> list = new ArrayList<>();
    public boolean findTarget(TreeNode root, int k) {
       traverse(root,list);
       int m=0;
       int n=list.size()-1;
       while (m<n){
           if (list.get(m)+list.get(n)==k)
               return true;
           else if (list.get(m)+list.get(n)>k)
               n--;
           else
               m++;
       }
       return false;
    }

    private void traverse(TreeNode root, List<Integer> list) {
        if (root==null)
            return;
        traverse(root.left,list);
        list.add(root.val);
        traverse(root.right,list);
    }
}
